Accurate and reliable time information is necessary for many systems and applications involving distributed resources, including networked systems and processes typified by the Internet. In such systems, different functional elements are required to have their clocks synchronized. Clock synchronization involves two aspects: frequency synchronization and time synchronization. The former means that element clocks run at the same frequency, and the latter means that elements agree at a particular epoch with respect to the coordinated universal time (UTC), i.e., there is no offset between element clocks. For many purposes, it is appropriate to focus on estimating clock offset and to assume higher order effects, such as the frequency offset, can be ignored or provided for separately.
One application in which clock synchronization becomes essential is in the transport of speech packets over the Internet. Thus, for example, if a network element knows the scheduled playout time of a voice packet at a destination and shares a common notion of time with the destination, it can schedule the transmission of the voice packet to the destination accordingly. Alternatively, if the network element knows that the playout time for the voice packet has passed, it can discard the packet and avoid unnecessarily transmitting it to the destination where it would be discarded anyway. Another example application in which synchronization proves necessary is in the transport of packets from a core network to base stations in a wireless network. That is, transmission of packets on a radio link (e.g., from the base station to the mobile device) is usually synchronous, and it is important to ensure that the core network delivers the packet to the base station in time.
In certain wireless cellular systems, it is possible to transmit multiple copies of the same frame from different base stations to a mobile device whenever the mobile device can receive a sufficiently strong average signal from both base stations, although there will still be instantaneous variations on the received signal due to fast fading. The mobile device then combines the multiple copies prior to decoding. In an unreliable radio environment this greatly improves the probability that the frame is received correctly due to signal diversity. This technique, called soft handoff or sometimes macrodiversity, relies on the fact that the transmissions from the multiple base stations are synchronized in time, so that the mobile can combine the copies without ambiguity. In this context as well it is important for a common notion of time across multiple base stations when needed and an efficacious way to achieve this is through the mechanism and processing technique described in this invention. Therefore, it is often important that the base stations be synchronous with the core network.
Synchronizing the clocks is a two step process: first, the magnitude of the offset between the clocks is estimated, and then one of the clocks is adjusted, as needed. Clocks inherently tend to drift and therefore offset estimation and correction must be done on a continuing basis.
Clock synchronization issues have been extensively addressed in the literature. See, for example, D. Mills, Internet time synchronization: the Network Time Protocol, IEEE Trans. Communications, Vol. 39, No. 10, October 1991; D. Mitra, Network synchronization: analysis of a hybrid of master-slave and mutual synchronization, IEEE Trans. Communications, COM-28, 8 (August 1980), pp. 1245-1259; and N. W. Rickert, Non Byzantine clock synchronization—a programming experiment, ACM Operating Systems Review 22,1 (January 1988), pp. 73-78.
A well-known clock synchronization protocol that has been successfully deployed in the Internet is the Network Time Protocol (NTP), described, for example, in D. Mills, Network Time Protocol (version 3) Specification, Implementation and Analysis RFC 1305, March 1992. One of the most important network clock synchronization issues addressed by NTP is how to use the collected data to estimate the clock offset between a pair of network elements.
In V. Paxson, On Calibrating Measurements of Packet Transit Times, LBNL-41535, ftp://ftp.ee.lbl.gov/papers/vp-clocks-sigmetrics98.ps.gz, March, 1998 (and in a shortened paper with the same title published in Proc. ACM Sigmetrics98, Jun. 22-26, 1998), the author proposed a new algorithm for clock offset estimation. For easy reference, this algorithm will be referred to as the Separate Direction Estimation Algorithm (SDEA) and the cited papers as Paxson. While SDEA can provide improved performance relative to the NTP algorithm, SDEA nevertheless suffers from significant limitations, especially in applying SDEA to contexts in which loading is different for each of the directional links between pairs of network elements. The incorporated application describes techniques by which limitations of the NTP algorithm and SDEA are overcome and SDEA techniques are extended and improved. Increasingly stringent demands on network performance have caused workers in the field to seek other broadly applicable improved clock offset estimation techniques.